Combining a Memetic Algorithm with Integer Programming to Solve the Prize-Collecting Steiner Tree Problem^*

Gunnar W. Klau¹, Ivana Ljubi¹, Andreas Moser¹, Petra Mutzel¹, Philipp Neuner¹, Ulrich Pferschy², Günther Raidl¹, and René Weiskircher¹

¹Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstraße 9–11/186, 1040 Vienna, Austria
klau@ads.tuwien.ac.at
ljubic@ads.tuwien.ac.at
moser@ads.tuwien.ac.at
mutzel@ads.tuwien.ac.at
neuner@ads.tuwien.ac.at
raidl@ads.tuwien.ac.at
weiskircher@ads.tuwien.ac.at

²Department of Statistics and Operations Research, University of Graz, Austria
pferschy@uni-graz.at

Abstract. The prize-collecting Steiner tree problem on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total profit of all vertices not contained in the subtree. For this well-known problem we develop a new algorithmic framework consisting of three main parts:

(1) An extensive preprocessing phase reduces the given graph without changing the structure of the optimal solution. (2) The central part of our approach is a memetic algorithm (MA) based on a steady-state evolutionary algorithm and an exact subroutine for the problem on trees. (3) The solution population of the memetic algorithm provides an excellent starting point for post-optimization by solving a relaxation of an integer linear programming (ILP) model constructed from a model for finding the minimum Steiner arborescence in a directed graph.

Extensive experiments on benchmark instances from the literature show that our combination of an MA with ILP-based post-optimization compares favorably with previously published results. While our solution values are almost always the same (not surprisingly, since an extension of our ILP approach shows the optimality of these values), we obtain a significant reduction of running time for medium and large instances.

^*Partly supported by the Doctoral Scholarship Program of the Austrian Academy of Sciences (DOC) and by the Austrian Science Fund (FWF), grant P16263-N04.

LNCS 3102, p. 1304 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004